package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 单词拆分 II
 */

public class Code140 {
    public static void main(String[] args) {

    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>(), cur = new ArrayList<>();
        backtrace(s, 0, cur, ans, wordDict);
        return ans;
    }

    private void backtrace(String s, int index, List<String> cur, List<String> ans, List<String> wordDict) {
        if (index == s.length()) {
            ans.add(String.join(" ", cur));
            return;
        }
        for (String word : wordDict) {
            if (s.startsWith(word, index)) {
                cur.add(word);
                backtrace(s, index + word.length(), cur, ans, wordDict);
                cur.remove(cur.size() - 1);
            }
        }
    }
}
